Sejak dahulu lagi di Australia, orang asli telah mengadakan upacara dan ritual agama animis Dreamtime. Kehadiran kekal Kristian di Australia bagaimanapun, datang bersama kedatangan kapal banduan First Fleet British di Sydney pada tahun 1788. Sebagai tanah jajahan British, mazhab Kristian yang utama ialah Gereja England, tetapi satu per sepuluh daripada semua banduan yang datang ke Australia dengan Armada Pertama ialah Katolik, dan sekurang-kurangnya separuh daripada mereka telah dilahirkan di Ireland.[37]

Sebahagian kecil daripada marin British juga Katolik. Sebahagian daripada banduan Ireland telah diangkut ke Australia bagi jenayah politik atau pemberontakan sosial di Ireland, jadi pihak berkuasa mencurigai agama minoriti untuk tiga dekad pertama penempatan.[38] Anak-anak kapal penjelajah Perancis La Pérouse yang menjalankan upacara Katolik pertama di tanah Australia pada tahun 1788 – pengebumian Paderi Louis Receveur, seorang rahib Franciscan, yang meninggal dunia ketika kapal-kapal itu berlabuh di Botany Bay, dalam misi untuk meneroka Pasifik.[39]

Pada zaman awal penjajahan, paderi Gereja England bekerja rapat dengan gabenor. Richard Johnson, paderi Anglikan untuk Armada Pertama, dituduh oleh gabenor, Arthur Phillip, dengan meningkatkan "moral awam" di tanah jajahan, tetapi dia juga banyak terlibat dalam kesihatan dan pendidikan.[40] Reverend Samuel Marsden (1765–1838) mempunyai tugas majistret, dan sebagainya telah disamakan dengan pihak berkuasa oleh banduan. Beliau dikenali sebagai 'pendeta sebatan' untuk keterukan hukumannya[41]

Banduan Katolik telah dipaksa hadir Gereja England dan anak-anak mereka dan anak-anak yatim dibesarkan oleh pihak berkuasa sebagai Protestan.[42] Paderi Katolik pertama penjajah tiba di Australia sebagai banduan pada 1800 – James Harold, James Dixon, dan Peter O'Neill, yang telah disabitkan 'bersubahat' dalam Pemberontakan 1798 Ireland. Dixon telah dibebaskan dengan syarat dan dibenarkan untuk meraikan Massa. Pada 15 Mei 1803, dalam pakaian yang dibuat dari langsir dan dengan piala yang diperbuat daripada tin beliau mengadakan Massa Katolik pertama di New South Wales.[42]

Pemberontakan Castle Hill yang dimulakan Ireland pada 1804 mencemaskan pihak berkuasa British dan kebenaran Dixon untuk meraikan Massa telah dibatalkan. Jeremiah Flynn, Cistercian Ireland, telah dilantik sebagai Pengawas Apostolik New Holland, dan berangkat dari Britain ke tanah jajahan, tanpa diundang. Diperhatikan oleh pihak berkuasa, Flynn secara rahsia melaksanakan tugas paderi sebelum ditahan dan dihantar pulang ke London. Reaksi kepada urusan di Britain membawa kepada dua paderi lagi dibenarkan untuk membuat perjalanan ke Koloni pada tahun 1820 – John Joseph Therry dan Philip Connolly.[38] Batu asas untuk Katedral St Mary, Sydney yang pertama diletakkan pada 29 Oktober 1821 oleh Gabenor Lachlan Macquarie.

Ketiadaan misi Katolik di Australia sebelum 1818 mencerminkan ketidakupayaan undang-undang Katolik di Britain dan kedudukan Ireland yang sukar dalam Empayar British. Oleh itu, kerajaan meluluskan Benedictine Inggeris untuk memimpin gereja awal koloni.[43] Gereja England hilang keistimewaan undang-undang di Koloni New South Wales oleh Akta Gereja 1836. Digubal oleh reformis peguam besar John Plunkett, Akta tersebut menetapkan kesaksamaan undang-undang untuk Anglikan, Katolik dan Presbiterian dan kemudiannya diperluaskan kepada Metodis.[44] Catholic missionary William Ullathorne criticised the convict system, publishing a pamphlet, The Horrors of Transportation Briefly Unfolded to the People, in Britain in 1837.[45] Caroline Chisolm melakukan kerja-kerja menyatupadukan mazhab Kristian untuk mengurangkan penderitaan pendatang perempuan.

Pada mulanya, pendidikan adalah tidak formal terutamanya yang berlaku di rumah. Atas dorongan daripada Perdana Menteri Britain, Duke Wellington, dan dengan naungan Raja William IV, sekolah bebas tertua yang masih bertahan di Australia, The King's School, Parramatta, telah ditubuhkan pada tahun 1831 sebagai sebahagian daripada usaha untuk menubuhkan sekolah tatabahasa di tanah jajahan.[46] By 1833, there were around ten Catholic schools in the Australian colonies.[38] Hari ini seorang daripada lima pelajar Australia belajar di sekolah Katolik.[47]

Biskop Katolik pertama Sydney, John Bede Polding meminta komuniti biarawati dihantar ke tanah jajahan dan lima orang Sisters of Charity Ireland tiba pada tahun 1838 untuk menuruskan penjagaan dan bimbingan banduan wanita dan kerja-kerja di sekolah-sekolah dan hospital sebelum beralih untuk mengasaskan sekolah dan hospital mereka sendiri.[48] Atas permintaan Polding, Christian Brothers tiba di Sydney pada tahun 1843 untuk membantu di sekolah. Dengan menetap di Sevenhill terlebih dahulu, di Australia Selatan pada tahun 1848, Jesuit ialah paderi aliran keagamaan pertama memasuki dan mendirikan rumah-rumah di Australia Selatan, Victoria, Queensland dan Wilayah Utara – di mana mereka menubuhkan sekolah-sekolah dan misi.

Beberapa lagu rakyat Australia dijejak kembali ke tempoh ini.

Antara kerja-kerja pertama kesusasteraan Australia sebenar dihasilkan sepanjang tempoh ini ialah kisah penempatan Sydney oleh Watkin Tench, kapten marin First Fleet tiba pada 1788. Pada 1819, penyair, pengembara, wartawan dan ahli politik William Wentworth menerbitkan buku pertama yang ditulis oleh seorang rakyat Australia: A Statistical, Historical, and Political Description of the Colony of New South Wales and Its Dependent Settlements in Van Diemen's Land, With a Particular Enumeration of the Advantages Which These Colonies Offer for Emigration and Their Superiority in Many Respects Over Those Possessed by the United States of America (Sebuah Keterangan Statistik, Sejarah dan Politik Koloni New South Wales dan Penempatan Tanggungannya di Van Diemen's Land, Dengan Perincian Penyenaraian Kelebihan Yang Koloni Ini Tawarkan untuk Penghijrahan dan Penguasaan Mereka Dalam Banyak Aspek Mengatasi Mereka di Amerika Syarikat),[49] di mana beliau menyokong perkumpulan yang dipilih untuk New South Wales, perbicaraan oleh juri dan penempatan Australia oleh emigran bebas dan bukannya banduan. Pada tahun 1838 The Guardian: a tale oleh Anna Maria Bunn telah diterbitkan di Sydney. Ia merupakan novel pertama Australia yang dicetak dan disiarkan di tanah besar Australia dan novel Australia pertama yang ditulis oleh seorang wanita. Ia adalah sebuah fiksyen percintaan Gothik.[50]

Tradisi teater Australia Eropah juga datang dengan First Fleet, dengan pementasan pertama yang dilakukan pada tahun 1789 oleh banduan : The Recruiting Officer oleh George Farquhar.[51] Dua abad kemudian, keadaan yang luar biasa daripada asas-asas teater Australia telah diceritakan dalam Our Country's Good oleh Timberlake Wertenbaker: para peserta ialah banduan diperhatikan oleh pengawal sadis dan pelakon wanita utama adalah di bawah ancaman hukuman mati. Pementasan ini adalah berdasarkan kepada novel Thomas Keneally The Playmaker.[51] Theatre Royal, Hobart, dibuka pada tahun 1837 dan ia kekal teater tertua di Australia.[52] [Melbourne Athenaeum]] merupakan salah satu institusi awam tertua di Australia, yang diasaskan pada tahun 1839 dan ia berkhidmat sebagai perpustakaan, sekolah seni dan dewan tarian (dan kemudiannya menjadi pawagam pertama di Australia, penyaringan The Story of the Kelly Gang, filem pertama di dunia pada tahun 1906).[53] Queen's Theatre, Adelaide dibuka dengan Shakespeare pada tahun 1841 dan hari ini teater tertua di tanah besar.[54]